#include "Calculate.h"

Calculate::Calculate() {
    FlightData.resize(1); QueryPointData.resize(1); QueryPointData_Point.resize(1);
    FlightData[0].push_back(L"飞行线编号"); FlightData[0].push_back(L"飞行线端点1坐标"); FlightData[0].push_back(L"飞行线端点2坐标"); //FlightData[0].push_back(L"查询点到飞行线距离");
    QueryPointData[0].push_back(L"查询点坐标"); QueryPointData[0].push_back(L"距离最近的飞行线编号"); QueryPointData[0].push_back(L"距离大小");
    QueryPointData_Point[0].push_back(L"查询点坐标");
}

int Calculate::Get_Flight_num() {
    return Flight_num;
}

int Calculate::Get_QueryPoint_num() {
    return QueryPoint_num;
}

wstring Calculate::Point_wstringtext(int num) {
    return  QueryPointData_Point[num + 1][0];
}

void Calculate::Get_FlightDataReference(vector<vector<wstring>>& newdata) {
    newdata = FlightData;
}

void Calculate::Get_QueryPointDataReference(vector<vector<wstring>>& newdata) {
    newdata = QueryPointData;
}

void Calculate::Get_QueryPointData_PointReference(vector<vector<wstring>>& newdata) {
    newdata = QueryPointData_Point;
}

int Calculate::Read_txtFile(wstring Wstring_file_path) {
    ifstream file;
    file.open(Wstring_file_path, ios::in);
    // 判断文件是否打开成功
    if (!file.is_open())
    {
        return 0;
    }
    if (file >> Flight_num >> QueryPoint_num) {
        //if (cs == 2) {
        //    cout << Flight_num << "\n";
        //}
        //cs++;
        FlightData.resize(Flight_num + 1);
        for (int i = 1; i < FlightData.size(); ++i) {
            FlightData[i].resize(0);
        }
        QueryPointData.resize(QueryPoint_num + 1);
        for (int i = 1; i < QueryPointData.size(); ++i) {
            QueryPointData[i].resize(0);
        }
        QueryPointData_Point.resize(QueryPoint_num + 1);
        for (int i = 1; i < QueryPointData_Point.size(); ++i) {
            QueryPointData_Point[i].resize(0);
        }

        FlightLines.clear();
        FlightLines.resize(Flight_num);
        QueryPoints.clear();
        QueryPoints.resize(QueryPoint_num);


        for (int i = 1; i <= Flight_num; ++i) {
            FlightData[i].push_back(to_wstring(i)); //编号输入
            int four = 4, x1, y1, x2, y2;
            file >> x1 >> y1 >> x2 >> y2;
            FlightLines[i - 1].x1 = x1;
            FlightLines[i - 1].y1 = y1;
            FlightLines[i - 1].x2 = x2;
            FlightLines[i - 1].y2 = y2;
            FlightLines[i - 1].id = i;
            wstring xy = L"(" + to_wstring(x1) + L"," + to_wstring(y1) + L")";
            FlightData[i].push_back(xy);
            xy = L"(" + to_wstring(x2) + L"," + to_wstring(y2) + L")";
            FlightData[i].push_back(xy);
        }
        for (int i = 1; i <= QueryPoint_num; ++i) {
            //QueryPointData[i].push_back(to_wstring(i)); //编号输入
            int two = 2, x3, y3;
            file >> x3 >> y3;
            QueryPoints[i - 1].x = x3;
            QueryPoints[i - 1].y = y3;
            wstring xy = L"(" + to_wstring(x3) + L"," + to_wstring(y3) + L")";
            QueryPointData[i].push_back(xy);
            QueryPointData_Point[i].push_back(xy);
        }
    }
    else {
        return -1;
    }
    //for (int i = 0; i < QueryPoints.size(); ++i) {
    //    cout << QueryPoints[i].x << " " << QueryPoints[i].y << "\n";
    //}
    //findNearestFlightLine(FlightLines, QueryPoints);
    findNearestFlightLineKDTree(FlightLines, QueryPoints);

    /* results = findNearestFlightLine(FlightLines,QueryPoints);
     for (int i = 1; i <= results.size(); ++i) {
         QueryPointData[1].push_back(to_wstring(results[i]));
         QueryPointData[1].push_back();
     }
     */
    file.close();
    return 1; // 这里原代码没写返回值，补充返回1表示成功
}

// 构建KD树
shared_ptr<KDNode> Calculate::buildKDTree(vector<FlightLine>& flightLines, int depth) {
    if (flightLines.empty()) return nullptr;

    // 选择分割轴（交替按x或y轴分割）
    int axis = depth % 2;

    // 按当前轴排序
    sort(flightLines.begin(), flightLines.end(), [axis](const FlightLine& a, const FlightLine& b) {
        double a_mid = (axis == 0) ? (a.x1 + a.x2) / 2 : (a.y1 + a.y2) / 2;
        double b_mid = (axis == 0) ? (b.x1 + b.x2) / 2 : (b.y1 + b.y2) / 2;
        return a_mid < b_mid;
        });

    // 取中点作为当前节点
    int mid = flightLines.size() / 2;
    double mid_x = (flightLines[mid].x1 + flightLines[mid].x2) / 2;
    double mid_y = (flightLines[mid].y1 + flightLines[mid].y2) / 2;
    auto node = make_shared<KDNode>(mid_x, mid_y, flightLines[mid].id);

    // 递归构建左右子树
    vector<FlightLine> leftLines(flightLines.begin(), flightLines.begin() + mid);
    vector<FlightLine> rightLines(flightLines.begin() + mid + 1, flightLines.end());
    node->left = buildKDTree(leftLines, depth + 1);
    node->right = buildKDTree(rightLines, depth + 1);

    return node;
}

// 计算两点距离的平方（避免开方提高效率）
double Calculate::distanceSquared(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return dx * dx + dy * dy;
}

// KD树最近邻搜索
void Calculate::nearestNeighborSearch(shared_ptr<KDNode> node, const QueryPoint& query, int depth, double& minDist, int& nearestId) {
    if (!node) return;

    double currentDist = distanceSquared(query.x, query.y, node->point[0], node->point[1]);
    if (currentDist < minDist) {
        minDist = currentDist;
        nearestId = node->id;
    }

    int axis = depth % 2;
    bool goLeft = (axis == 0) ? (query.x < node->point[0]) : (query.y < node->point[1]);

    // 优先搜索更可能包含最近邻的分支
    if (goLeft) {
        nearestNeighborSearch(node->left, query, depth + 1, minDist, nearestId);
    }
    else {
        nearestNeighborSearch(node->right, query, depth + 1, minDist, nearestId);
    }

    // 检查另一分支是否可能有更近的点
    double remainingDist = (axis == 0) ?
        (query.x - node->point[0]) * (query.x - node->point[0]) :
        (query.y - node->point[1]) * (query.y - node->point[1]);
    if (remainingDist < minDist) {
        if (goLeft) {
            nearestNeighborSearch(node->right, query, depth + 1, minDist, nearestId);
        }
        else {
            nearestNeighborSearch(node->left, query, depth + 1, minDist, nearestId);
        }
    }
}

// 计算点到线段的最短距离（与之前相同）
double Calculate::pointToLineDistance(double px, double py, double x1, double y1, double x2, double y2) {
    double dx = x2 - x1;
    double dy = y2 - y1;
    double lineLengthSq = dx * dx + dy * dy;

    if (lineLengthSq == 0) {
        return sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));
    }

    double t = ((px - x1) * dx + (py - y1) * dy) / lineLengthSq;
    t = max(0.0, min(1.0, t));

    double projectionX = x1 + t * dx;
    double projectionY = y1 + t * dy;

    return sqrt((px - projectionX) * (px - projectionX) + (py - projectionY) * (py - projectionY));
}

// 使用KD树优化查找最近飞行线
vector<int> Calculate::findNearestFlightLineKDTree(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints) {
    // 构建KD树（需要非const，所以复制一份）
    vector<FlightLine> linesCopy = flightLines;
    auto root = buildKDTree(linesCopy);
    int num = 1; //后加入的代码
    vector<int> results;
    for (const auto& qp : queryPoints) {
        double minDist = 99999999999999;
        int nearestId = -1;

        // 先用KD树找到最近的中点（近似解）
        nearestNeighborSearch(root, qp, 0, minDist, nearestId);

        // 由于KD树存储的是中点，我们需要在所有飞行线中精确计算距离
        // 但可以只检查KD树返回的候选飞行线，减少计算量
        double exactMinDist = 99999999999999;
        int exactNearestId = -1;
        for (const auto& line : flightLines) {
            double dist = pointToLineDistance(qp.x, qp.y, line.x1, line.y1, line.x2, line.y2);
            if (dist < exactMinDist) {
                exactMinDist = dist;
                exactNearestId = line.id;
            }
        }
        QueryPointData[num].push_back(to_wstring(exactNearestId));  //后加入的代码
        QueryPointData[num].push_back(to_wstring(exactMinDist));//后加入的代码
        results.push_back(exactNearestId);
        ++num; //后加入的代码
    }
    return results;
}


//暴力方法求解最近飞行线
void Calculate::findNearestFlightLine(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints) {
    vector<int> results;
    int num = 1; //后加入的代码
    for (const auto& qp : queryPoints) {
        double minDistance = 1.7976931348623157e+308;
        int nearestLineId = -1;
        for (const auto& line : flightLines) {
            double distance = pointToLineDistance(qp.x, qp.y, line.x1, line.y1, line.x2, line.y2);
            if (distance < minDistance) {
                minDistance = distance;
                nearestLineId = line.id;
            }
        }
        QueryPointData[num].push_back(to_wstring(nearestLineId));  //后加入的代码
        QueryPointData[num].push_back(to_wstring(minDistance));//后加入的代码
        results.push_back(nearestLineId);
        ++num; //后加入的代码
    }
    return;
    //return results;
}

